package 剑指offer;

import java.util.Scanner;


/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:40:25 
* @Description：
* 
输入一个链表，反转链表后，输出新链表的表头。
*/



/*

head为第一个结点指针
用pre记录当前节点的前一个节点
用next记录当前节点的后一个节点

1.当前节点a不为空，进入循环，先记录a的下一个节点位置next = b;再让a的指针指向pre
2.移动pre和head的位置，正因为刚才记录了下一个节点的位置，所以该链表没有断，我们让head走向b的位置。
3.当前节点为b不为空，先记录下一个节点的位置，让b指向pre的位置即a的位置，同时移动pre和head
4.当前节点c不为空，记录下一个节点的位置，让c指向b，同时移动pre和head，此时head为空，跳出，返回pre。
 */



public class A15反转链表 {

	public static ListNode ReverseList(ListNode head) {


		// 判断链表为空或长度为1的情况
		if (head == null || head.next == null) {
			return head;
		}
		
		ListNode pre = null;            // pre指针，用于记录当前结点的前一个结点地址
		ListNode next = null;            // next指针，用于记录当前结点的下一个结点地址
		
		while (head != null) { 			// head指向null时，循环终止。
			next = head.next;            // 记录当前节点的下一个节点位置；先用next指针记录当前结点的下一个结点地址。
			head.next = pre;            	// 让当前节点指向前一个节点位置，完成反转。让被当前结点与链表断开并指向前一个结点pre。
			pre = head;                     // pre指针指向当前结点，pre 往右走
			head = next;                   // // 当前节点往右继续走，head指向next(保存着原链表中head的下一个结点地址)
		}
		return pre;// 当循环结束时,pre所指的就是反转链表的头结点
	}
	
	
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
        String[] array=scan.nextLine().split(" ");
        ListNode Head=new ListNode(Integer.parseInt(array[0]));
        ListNode nextNode=Head;
        for(int i=1;i<array.length;i++){
            ListNode newNode=new ListNode(Integer.parseInt(array[i]));
            nextNode.next=newNode;
            nextNode=newNode;
        }
        ListNode p = ReverseList(Head);
       while (p!=null) {
    	   System.out.print(p.val+" ");
    	   p=p.next;
	}
        
	}
	
}
